#include <iostream>
#include <stack>

using namespace std;
// 32. 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
// 示例 1：
// 输入：s = "(()"
// 输出：2
// 解释：最长有效括号子串是 "()"

class Solution {
public:
    int longestValidParentheses(string s) {
        size_t ans = 0;
        stack<size_t> st;
        st.push(-1);
        for(size_t i = 0; i < s.length(); i++) {
            if(s[i] == '(') // 左括号下标入栈
                st.push(i);
            else {  // 遇到右括号
                if(!st.empty()) {
                    st.pop();   // 先弹出栈顶
                    if(st.empty())
                        st.push(i);
                    else {
                        ans = max(ans, i-st.top());
                    }
                }
            }
        }
        return (int)ans;
    }
};

int main() {
    cout << Solution().longestValidParentheses("(()") << endl; // 2
    cout << Solution().longestValidParentheses(")()())") << endl; // 4
    cout << Solution().longestValidParentheses("") << endl; // 0

    return 0;
}
